//
// Created by wormtql on 2020/11/8.
//

#include <map>
#include <string>
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <set>
#include <cmath>

#define INF 0x3f3f3f3f

using namespace std;

struct Edge {
    int to;
    int from;
    int next;
};

// 图
#ifdef REMOTE
Edge edges[5000000];
int edge_count = 0;
int head[600000];
int node_count = 0;
int dis[600000];
int vis[600000];
int parent[600000];
#else
Edge edges[2000000];
int edge_count = 0;
int head[500000];
int node_count = 0;
int dis[500000];
int vis[500000];
int parent[500000];
#endif
map<string, int> name2id;
map<int, string> id2name;

// trace总node数
int trace_node_count = 0;
int trace_found_node_count = 0;

int matrix[10000][10000];

void init() {
    memset(edges, -1, sizeof(edges));
    memset(head, -1, sizeof(head));
    edge_count = 0;
    node_count = 0;
    name2id.clear();

    trace_node_count = 0;
    trace_found_node_count = 0;

    memset(matrix, INF, sizeof(matrix));
}

bool parseLine(const char * line, char * from, char * to) {
    int i = 0;
    bool flag = false;
    bool isFrom = true;

    int a = 0;
    int b = 0;

    while (line[i] != '\0') {
        if (line[i] == '\"') {
            if (!flag) {
                flag = true;
            } else {
                if (!isFrom) {
                    break;
                }
                flag = false;
                isFrom = false;
            }
            i++;
            continue;
        }

        if (flag) {
            if (isFrom) {
                from[a] = line[i];
                a++;
            } else {
                to[b] = line[i];
                b++;
            }
        }
        i++;
    }

    if (a == 0 || b == 0) {
        return false;
    }

    from[a] = 0;
    to[b] = 0;

    return true;
}

void parse_csv_line(char * line, vector<string> & data) {
    int state = 0;
    char buf[1000] = { 0 };
    int l = 0;

    int i = 0;
    while (line[i]) {
        if (state == 0) {
            if (line[i] == ',') {
                state = 1;
            } else {
                buf[l++] = line[i];
                i++;
            }
        } else if (state == 1) {
            buf[l] = 0;
            l = 0;
            data.push_back(string(buf));
            i++;
            state = 0;
        }
    }
    if (l != 0) {
        buf[l] = 0;
        data.emplace_back(buf);
    }
}

int register_node(char * name) {
    string temp(name);
    if (name2id.find(temp) == name2id.end()) {
        name2id[name] = node_count;
        id2name[node_count] = name;
        node_count++;
        return node_count - 1;
    } else {
        return name2id[temp];
    }
}

void add(int from, int to) {
    edges[edge_count].from = from;
    edges[edge_count].to = to;
    edges[edge_count].next = head[from];
    head[from] = edge_count;
    edge_count++;
}

bool load_graph(char * filename) {
    ifstream file(filename);

    if (!file.is_open()) {
        return false;
    }

    char line[1000] = { 0 };
    while(file.getline(line, 1000)) {
        char from[100] = { 0 };
        char to[100] = { 0 };

        bool ret = parseLine(line, from, to);
        if (!ret) {
            printf("aaa\n");
            continue;
        }

        int from_id = register_node(from);
        int to_id = register_node(to);
        add(from_id, to_id);
    }

    return true;
}

void sp_single(int a) {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    queue<int> q;
    q.push(a);
    dis[a] = 0;
    vis[a] = 1;

    while(!q.empty()) {
        int p = q.front();
        q.pop();

        for (int e = head[p]; e != -1; e = edges[e].next) {
            int to = edges[e].to;

            if (!vis[to]) {
                q.push(to);
                vis[to] = 1;
                dis[to] = dis[p] + 1;
                parent[to] = p;
            }
        }
    }
}

bool load_function_list(char * filename, vector<int> & out) {
    ifstream file(filename);

    char buf[1000];
    while (file.getline(buf, 1000)) {
        vector<string> temp;
        parse_csv_line(buf, temp);
        if (!temp.empty()) {
            if (name2id.find(temp[0]) == name2id.end()) {
                return false;
            }
            out.push_back(name2id[temp[0]]);
        }
    }

    file.close();
    return true;
}

void write_file(ofstream & file, int c) {
    for (int i = 0; i < c; i++) {
        for (int j = 0; j < c; j++) {
            file << matrix[i][j];
            if (j != c - 1) {
                file << ",";
            }
        }
        file << endl;
    }
}

int main(int argc, char * argv[]) {
#ifdef REMOTE
    printf("running remotely\n");
#endif
    if (argc < 6) {
        printf("caching distance between every two nodes using nearest parent alg\n\n");
        printf("app <graph.dot(directed)> <function_list.csv> <start> <end+1> <outfile>\n\n");
        printf("graph.dot:          call graph\n");
        printf("function_list.csv:  function list\n");
        printf("start, end:         range in node count\n");
        printf("outfile:            output matrix\n");
        return 0;
    }

    init();

    // load graph
    bool ret = load_graph(argv[1]);
    if (!ret) {
        printf("unable to open file \"%s\"\n", argv[1]);
    }
    printf("graph loaded\n");
    printf("node count: %d\n", node_count);
    printf("edge count: %d\n\n", edge_count);


    // load function list
    vector<int> function_id_list;
    ret = load_function_list(argv[2], function_id_list);
    if (!ret) {
        printf("function not found\n");
        return 0;
    }
    int function_count = function_id_list.size();

    int start = atoi(argv[3]);
    int end = atoi(argv[4]);
    end = min(end, node_count);

    for (int i = start; i < end; i++) {
        sp_single(i);

        for (int j = 0; j < function_count; j++) {
            for (int k = 0; k < function_count; k++) {
                int d = dis[function_id_list[j]] + dis[function_id_list[k]];

                matrix[j][k] = min(matrix[j][k], d);
            }
        }

        if (i % 100 == 0 || i == end - 1) {
            ofstream out_file(argv[5]);
            write_file(out_file, function_count);
            out_file.close();
            printf("#%d, %.6lf%%\n", i + 1, (i + 1.0 - start) / (end - start));
        }
    }


    return 0;
}